package 剑指offer;

/**
 * @author zhangmin
 * @create 2021-12-11 19:30
 */
public class day31_142_43_44 {
    /**==============================================================================================================================================
     * 剑指 Offer 14- II. 剪绳子 II
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？答案需要取模 1e9+7（1000000007）
     * 推论一： 将绳子 以相等的长度等分为多段 ，得到的乘积最大。二：尽可能以长度3分割时，乘积最大
     * 思路：当n<=3时，不应再分，但是要求m > 1所有分成n-1返回
     * 当n>3时，n除以3得到整数部分为a,余数部分为b
     * 当b==0时，返回3^a
     * 当b==1时，最后一个4应该分成2*2，所以返回：3^(a-1)*2*2
     * 当b==2时，返回:3^(a)*2;
     *  */
    public int cuttingRope(int n) {
        int mod=1000000007;
        if(n<=3) return (n-1)%mod;
        int b=n%3;
        long rem=1,x=3;
        for (int a = n/3-1; a >0 ; a/=2) {
            if (a%2==1) rem=(rem*x)%mod;
            x=(x*x)%mod;
        }
        if (b==0){
            return (int) (rem*3%mod);
        }else if (b==1){
            return (int) (rem*4%mod);
        }else {
            return (int) (rem*6%mod);
        }
    }
    /**==============================================================================================================================================
     * 剑指 Offer 43. 1～n 整数中 1 出现的次数
     * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
     * 设数字 n 是个 x 位数，记 n 的第 i 位为 n_i，则可将 n 写为nx,nx−1⋯n2,n1
     * 称 "ni" 为 当前位 ，记为 cur,将“ni-1ni-2...n2n1"为低位，low；将“nxnx-1...ni+1”为high
     * 将 10^i称为 位因子 ，记为 digit
     * 当 cur = 0时： 此位 1 的出现次数只由高位 high 决定，计算公式为：high×digit
     * 当 cur = 1时： 此位 1 的出现次数由高位 high 和低位 low 决定，计算公式为：high×digit+low+1
     * 当 cur=2,3,⋯,9 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：(high+1)×digit
     *
     *  */
    public int countDigitOne(int n) {
        int digit=1,res=0;
        //从最后一位开始
        int high=n/10,cur=n%10,low=0;
        // 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
        while (high!=0||cur!=0){
            if (cur==0) res+=high*digit;
            else if (cur==1) res+=high*digit+low+1;
            else res+=(high+1)*digit;
            low+=cur*digit;// 将 cur 加入 low ，组成下轮 low
            cur=high%10;//下轮 cur 是本轮 high 的最低位
            high/=10;//将本轮 high 最低位删除，得到下轮 high
            digit*=10;//位因子每轮 × 10
        }
        return res;
    }
    public int countDigitOne1(int n) {
        if (n<=9)return 1;
        long m=1;
        int re=0;
        for (int k = 0; n >=m ; k++) {
            re+=(n/(m*10))*m+Math.min(Math.max(n%(m*10)-m+1,0),m);
            m*=10;
        }
        return re;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 44. 数字序列中某一位的数字
     * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
     * 先计算这个位置的数字是在几位数上，在找出是哪个数子，最后判断是这个数字的哪一位
     * 可推出各 digit 下的数位数量 count 的计算公式：count=9×start×digit
     *  */
    public int findNthDigit(int n) {
        //1、确定所求数位的所在数字的位数
        int digit=1;
        long start=1,count=9;
        while (n>count){
            n-=count;
            digit+=1;//位数+1
            start=start*10; //开始数字位数也要上一位
            //计算digit位的数字有多少个
            count=9*start*digit;
        }
        //2、确定所求数位所在的数字：所求数位 在从数字 start 开始的第 [(n - 1) / digit] 个 数字 中
        //此时n已经减去了前面位数的个数
        long num=start+(n-1)/digit;
        //3、确定所求数位在 num 的哪一数位：所求数位为数字 num 的第 (n - 1) % digit 位
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }
}
